The subject matter of this application is related to the subject matter in a co-pending non-provisional application by Saqib J. Ahmad filed on the same day as the instant application, entitled, xe2x80x9cMethod and Apparatus for Deleting Objects From Memory within a Smart Card,xe2x80x9d having Serial Number TO BE ASSIGNED, and filing date TO BE ASSIGNED (Attorney Docket No. SUN-P7670-EKL).
The subject matter of this application is also related to the subject matter in a co-pending non-provisional application by the same inventor as the instant application, filed on the same day as the instant application, entitled, xe2x80x9cMemory Management System Supporting Object Deletion in Non-volatile Memoryxe2x80x9d, having Serial Number TO BE ASSIGNED, and filing date TO BE ASSIGNED(Attorney Docket No. SUN-P7698-EKL).
1. Field of the Invention
The present invention relates to the process of managing memory in a computer system. More specifically, the present invention relates to a method and an apparatus for freeing memory within a computing device, such as a smart card, which includes both volatile and non-volatile memory.
2. Related Art
Dramatic advances in computer technology presently make it possible to integrate a significant amount of computing power onto a xe2x80x9csmart cardxe2x80x9d. This increased computing power enables smart cards to support large numbers of applications. However, unlike conventional computing systems, smart card-based computing systems do not presently provide a mechanism for reclaiming memory occupied by objects that are no longer in use. This process of reclaiming unused memory is often referred to as xe2x80x9cgarbage collectionxe2x80x9d.
Garbage collection can be performed in conventional computing systems using a number of well-known techniques. However, smart card-based computing systems are different than conventional computing systems because objects can reside in writeable non-volatile memory, such as electrically erasable programmable read only memory (EEPROM) or flash memory. (Within this specification the term xe2x80x9cEEPROMxe2x80x9d refers to both xe2x80x9cEEPROMxe2x80x9d and xe2x80x9cflash memory.xe2x80x9d)
Existing garbage collection techniques are not suitable for EEPROM because individual memory elements in EEPROM can only be written to a limited number of times. Hence, existing garbage collection techniques, which operate by frequently marking objects in memory, can dramatically reduce the life expectancy of EEPROM. Moreover, the process of performing write operations to EEPROM is typically very slow, which can significantly degrade system performance.
Smart cards often contain a small amount of volatile random access memory (RAM), which does not suffer from the above-described problems of writeable non-nonvolatile memory. However, the amount of RAM is often extremely limited. Hence, it is not possible to store a complete image of EEPROM in RAM; even a bitmap representing blocks of EEPROM would take up too much space in RAM.
The garbage collection process operates by first deleting unused objects from memory. Once the objects are deleted, the memory space formerly occupied by the objects must somehow be reclaimed. In conventional computing systems, this reclamation process is typically accomplished by performing a compaction operation to eliminate xe2x80x9cholesxe2x80x9d in memory that arise as a consequence of deleting objects. However, a compaction operation typically involves rewriting a significant portion of memory, which tends to reduce the life expectancy of the EEPROM.
Hence, what is needed is a method and an apparatus for reclaiming memory without requiring the large number of write operations involved in performing a compaction operation.
Furthermore, in computing devices that include both EEPROM and RAM, it is possible to define xe2x80x9ctransient objects,xe2x80x9d which include a portion defined in EEPROM and a portion defined in RAM. In order to support such hybrid objects, what is needed is a method and an apparatus that reclaims memory used by these hybrid objects.
One embodiment of the present invention provides a system for compacting memory within a computing device, wherein the computing device supports transient objects, having a persistent portion stored in a writeable non-volatile memory, and a transient portion stored in a volatile memory. During the compaction process, the system resets the volatile memory so that information in the volatile memory is deleted. Next, the system scans through a list of objects. For each transient object encountered in the list of objects, the system allocates space for the transient object in the volatile memory. The system also updates the persistent portion of the transient object, if necessary, to specify a new location in volatile memory for the transient portion of the transient object.
In a variation on this embodiment, the compaction can occur during an initialization of the computing device, or during an initialization of a new application on the computing device.
In a variation on this embodiment, prior to resetting the volatile memory, the system determines if compaction is needed by checking state information in the writeable non-volatile memory, wherein the state information indicates whether a transient object has been deleted. In a further variation, the state information includes separate state information for different pools of volatile memory, thereby allowing compaction of specific pools of volatile memory, without having to compact all of the volatile memory. Note that a heap in volatile memory can be divided into a number of pools.
In a variation on this embodiment, the list of objects includes: a list of transient objects in a clear-on-reset heap within the volatile memory that are to be cleared on reset of the computing device; and a list of transient objects in a clear-on-deselect heap within the volatile memory that are to be cleared when an application running on the computing device is deselected.
In a variation on this embodiment, the writeable non-volatile memory can include: electrically erasable read only memory (EEPROM), flash memory, or a magnetic memory device.